Minimum Spanning Trees (MST)

A Minimum Spanning Tree (MST) finds the cheapest way to connect all vertices in a weighted, undirected graph $G=(V, E)$ . This is a global optimization problem, distinct from finding the shortest path between two specific points.

What it is: An MST is a subgraph $T \subseteq G$ that connects all vertices together with the minimum possible total edge weight, without forming any cycles.
Property 1: Spanning - The subgraph must connect all $|V|$ vertices of the original graph.
Property 2: Acyclic - The subgraph must not contain any cycles, which is the definition of a tree structure.
Property 3: Edge Count - A tree connecting $|V|$ vertices will always have exactly $|V|-1$ edges.
Property 4: Minimum Weight - The sum of all edge weights in the tree, $\sum w(u, v) \in T$ , is minimized.
Transition from SSSP: While Dijkstra's algorithm finds the shortest path from a single source, MST algorithms like Prim's use a similar greedy approach to build a minimal tree connecting all nodes.

MST vs. Shortest Path (SSSP)

Feature	Minimum Spanning Tree (MST)	Single-Source Shortest Path (SSSP)
Goal	Connect ALL vertices with minimum total weight.	Find shortest paths from ONE source to all others.
Output	A single tree (a subgraph).	A set of paths.
Edge Count	Exactly $\|V\|-1$ .	Varies, not fixed.
Structure	Guaranteed to be acyclic.	The original graph can have cycles.

📝 Interactive Quiz

1. What is the primary goal of an MST algorithm?

A) Find the shortest path between two nodes.
B) Connect all nodes with minimum total edge weight.
C) Find the longest possible path without cycles.
D) Visit every edge in the graph exactly once.

2. For a connected graph with 20 vertices ( $|V|=20$ ), how many edges will its MST have?

A) 20
B) It depends on the edge weights.
C) 19
D) 21

3. Which of the following is a required property of a Minimum Spanning Tree?

A) It must contain at least one cycle.
B) It must be acyclic.
C) It must include the heaviest edge from the graph.

KEY TIPS

💡 Key Tips

MST is Not Shortest Path

The path between two nodes in an MST is not necessarily the shortest path between them in the original graph.

Greedy Algorithms

MST algorithms like Prim's and Kruskal's are classic examples of greedy algorithms that make locally optimal choices to find a global optimum.

Connectivity Prerequisite

An MST can only be found for a connected graph. If the graph is disconnected, you would find a Minimum Spanning Forest.

Undirected Graphs

MSTs are typically defined for undirected, weighted graphs. The concept is less common for directed graphs.